/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */

var exist = function (board, word) {
    let row = board.length
    let col = board[0].length
    if (!board || !row || !col) {
        return false
    }
    // 初始化访问数组
    let visited = new Array(row)
    for (let i = 0; i < row; i++) {
        visited[i] = new Array(col)
    }
    let index = 0
    for (let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if (board[i][j] === word[index]) {
                if (dfs(i, j, word, index, visited, board)) {
                    return true
                }
            }
        }
    }
    return false
    function dfs(i, j, word, index, visited, board) {
        // 如果在范围外
        if (i < 0 || i >= row || j < 0 || j >= col || visited[i][j]) {
            return false
        }
        // 如果单词相同
        if (board[i][j] === word[index]) {
            // 并且是最后一个
            if (index === word.length - 1) {
                return true
            } else {
                visited[i][j] = true
                res = dfs(i + 1, j, word, index + 1, visited, board) ||
                    dfs(i, j + 1, word, index + 1, visited, board) ||
                    dfs(i - 1, j, word, index + 1, visited, board) ||
                    dfs(i, j - 1, word, index + 1, visited, board)
                visited[i][j] = false
                return res
            }
        }
    }
};